// FIT_6204_Gorodilov_GreedyDoc.cpp : implementation of the CFIT_6204_Gorodilov_GreedyDoc class
//

#include "stdafx.h"
#include "FIT_6204_Gorodilov_Greedy.h"
#include "FIT_6204_Gorodilov_GreedyDoc.h"

#include <omp.h>
#include <math.h>
#ifdef _DEBUG
#define new DEBUG_NEW
#endif


double **g_pDistanceMap;
// CFIT_6204_Gorodilov_GreedyDoc

IMPLEMENT_DYNCREATE(CFIT_6204_Gorodilov_GreedyDoc, CDocument)

BEGIN_MESSAGE_MAP(CFIT_6204_Gorodilov_GreedyDoc, CDocument)
END_MESSAGE_MAP()


// CFIT_6204_Gorodilov_GreedyDoc construction/destruction

CFIT_6204_Gorodilov_GreedyDoc::CFIT_6204_Gorodilov_GreedyDoc()
: m_ScrollSize(2000, 2000)
, m_IsTriangulationReady(FALSE)
{
	// TODO: add one-time construction code here
}

CFIT_6204_Gorodilov_GreedyDoc::~CFIT_6204_Gorodilov_GreedyDoc()
{
}
BOOL CFIT_6204_Gorodilov_GreedyDoc::OnNewDocument()
{
	if (!CDocument::OnNewDocument())
		return FALSE;

	m_Points.RemoveAll();
	m_IsTriangulationReady = false;
	UpdateAllViews(NULL);

	return TRUE;
}




// CFIT_6204_Gorodilov_GreedyDoc serialization

void CFIT_6204_Gorodilov_GreedyDoc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
		// TODO: add storing code here
	}
	else
	{
		// TODO: add loading code here
	}
}


// CFIT_6204_Gorodilov_GreedyDoc diagnostics

#ifdef _DEBUG
void CFIT_6204_Gorodilov_GreedyDoc::AssertValid() const
{
	CDocument::AssertValid();
}

void CFIT_6204_Gorodilov_GreedyDoc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG


// CFIT_6204_Gorodilov_GreedyDoc commands

const CSize CFIT_6204_Gorodilov_GreedyDoc::GetScrollSize(void) const
{
	return m_ScrollSize;
}

void CFIT_6204_Gorodilov_GreedyDoc::SetScrollSize(const CSize scrollSize)
{
	m_ScrollSize = scrollSize;
}

const CPoint CFIT_6204_Gorodilov_GreedyDoc::GetPoint(const UINT index)
{
	if (index >= GetCount()) {
		return 0;
	}
	return m_Points.GetAt(index);
}

const EDGE CFIT_6204_Gorodilov_GreedyDoc::GetEdge(const UINT index) {
	if (index >= GetEdgesCount()) {
		return EDGE();
	}
	return m_Edges.GetAt(index);
}

const UINT CFIT_6204_Gorodilov_GreedyDoc::GetCount(void) {
	return m_Points.GetSize();
}

UINT CFIT_6204_Gorodilov_GreedyDoc::PeekPoint(const CPoint point, int distance) {
	for (UINT index = 0; index < GetCount(); index++) {
		CPoint currentPoint = m_Points.GetAt(index);
		int x = (int)currentPoint.x - (int)point.x;
		int y = (int)currentPoint.y - (int)point.y;
		if (x * x + y * y <= distance * distance) {
			return index;
		}
	}
	return (UINT)-1;
}

void CFIT_6204_Gorodilov_GreedyDoc::DeletePoint(const CPoint point, int distance) {
	for (UINT index = 0; index < GetCount(); index++) {
		CPoint currentPoint = m_Points.GetAt(index);
		int x = (int)currentPoint.x - (int)point.x;
		int y = (int)currentPoint.y - (int)point.y;
		if (x * x + y * y <= distance * distance) {
			m_Points.RemoveAt(index);
			break;
		}
	}
	m_IsTriangulationReady = false;
}

UINT CFIT_6204_Gorodilov_GreedyDoc::AddPoint(const CPoint point)
{
	if (point.x >= 0 &&
		point.y >= 0 &&
		point.x < m_ScrollSize.cx && 
		point.y < m_ScrollSize.cy) {
		INT_PTR i = m_Points.Add(point);
		m_IsTriangulationReady = false;
		m_Points.GetAt(i);
		return m_Points.GetCount() - 1;
	}
	return NULL;
}


double CFIT_6204_Gorodilov_GreedyDoc::MakeGreedyTriangulation(void) {
	if (m_IsTriangulationReady) {
		return -1.0;
	}
	double L = 0.0;
	m_Edges.RemoveAll();
	UINT N = m_Points.GetCount();

	// Allocating memory
	double **distanceMap = new double*[N];
	for (UINT i = 0; i < N; i++) {
		distanceMap[i] = new double[N];
	}
	UINT edgesCount = (N*N - N) >> 1;
	EDGE *allEdges = new EDGE[edgesCount];
	
	// Calculation of edges length
	double maxLength = m_ScrollSize.cx + m_ScrollSize.cy;
	for (UINT row = 0; row < N; row++) {
		distanceMap[row][row] = maxLength;
	}
	for (UINT row = 0; row < N; row++) {
		CPoint a = m_Points[row];
		for (UINT column = 0; column < row; column++) {
			CPoint b = m_Points[column];
			double distance = GetEdgeLenght(a, b);
			distanceMap[row][column] = distance;
			distanceMap[column][row] = distance;
		}
	}
	
	// Prepare edges list
	g_pDistanceMap = distanceMap;
	for (UINT row = 0, count = 0; row < N; row++) {
		for (UINT column = 0; column < row; column++) {
			allEdges[count].a = row;
			allEdges[count].b = column;
			count++;
		}
	}
	qsort(allEdges, edgesCount, sizeof(*allEdges), compareEdges);

	for (UINT i = 0; i < edgesCount; i++) {
		EDGE ed = allEdges[i];
		if (TestEdge(ed)) {
			m_Edges.Add(ed);
			L += distanceMap[ed.a][ed.b];
		}
	}

	// Free allocated memory
	g_pDistanceMap = NULL;
	delete[] allEdges;
	for (UINT i = 0; i < N; i++) {
		delete[] distanceMap[i];
	}
	delete distanceMap;
	m_IsTriangulationReady = TRUE;
	return L;
}

const double CFIT_6204_Gorodilov_GreedyDoc::GetEdgeLenght(const CPoint &a, const CPoint &b) {
	double x = (a.x - b.x);
	double y = (a.y - b.y);
	return sqrt(x*x + y*y);
}

int compareEdges( const void *arg1, const void *arg2 ) {
	const EDGE* p1 = (const EDGE*)arg1;
	const EDGE* p2 = (const EDGE*)arg2;
	double distance1 = g_pDistanceMap[p1->a][p1->b];
	double distance2 = g_pDistanceMap[p2->a][p2->b];
	if (distance1 - distance2 < EPS) {
		if (distance2 - distance1 < EPS) {
			return 0;
		} else {
			return -1;
		}
	} else {
		return 1;
	}
}

BOOL CFIT_6204_Gorodilov_GreedyDoc::TestEdge(EDGE &edge1){
	UINT count = m_Edges.GetCount();
	for (UINT i = 0; i < count; i++) {
		if (IsEdgeCrossEdge(edge1, m_Edges[i])) {
			return FALSE;
		}
	}
	return TRUE;
}

BOOL CFIT_6204_Gorodilov_GreedyDoc::IsEdgeCrossEdge(EDGE &edge1, EDGE &edge2) {
	CPoint p1, p2, p3, p4;
	p1 = m_Points[edge1.a];
	p2 = m_Points[edge1.b];
	p3 = m_Points[edge2.a];
	p4 = m_Points[edge2.b];
	return IsLinesCross(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y);
}

BOOL IsLinesCross(UINT x1, UINT y1, UINT x2, UINT y2,
				  UINT x3, UINT y3, UINT x4, UINT y4)
{
	int k = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
	int k1 = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3);
	int k2 = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3);

	if (k == 0)
	{
		if ((k1 == 0) && (k2 == 0))
		{
			int tmp;
			if (x1 > x2)
			{
				tmp = x1;
				x1 = x2;
				x2 = tmp;
			}
			if (x3 > x4)
			{
				tmp = x3;
				x3 = x4;
				x4 = tmp;
			}
			if (y1 > y2)
			{
				tmp = y1;
				y1 = y2;
				y2 = tmp;
			}
			if (y3 > y4)
			{
				tmp = y3;
				y3 = y4;
				y4 = tmp;
			}
			if (((x3 < x2) && (x3 > x1)) ||
				((x4 < x2) && (x4 > x1)))
			{
				return TRUE;
			}
			return FALSE;
		}
		return FALSE;
	}

	double ua = (double)k1/k;
	double ub = (double)k2/k;
	if ((ua < 1) && (ua > 0) && (ub < 1) && (ub > 0))
	{
		return TRUE;
	}
	return FALSE;
}

BOOL CFIT_6204_Gorodilov_GreedyDoc::IsTriangulationReady(void) {
	return m_IsTriangulationReady;
}

const UINT CFIT_6204_Gorodilov_GreedyDoc::GetEdgesCount(void) {
	if (IsTriangulationReady()) {
		return m_Edges.GetCount();
	}
	return 0;
}

BOOL CFIT_6204_Gorodilov_GreedyDoc::UpdatePoint(UINT index, const CPoint point) {
	if (index >= GetCount()) {
		return FALSE;
	}
	m_Points[index] = point;
	m_IsTriangulationReady = false;
	return TRUE;
}

BOOL CFIT_6204_Gorodilov_GreedyDoc::Log(UINT N, double L, double T, int type) {
	LOGENTRY entry;
	entry.N = N;
	entry.L = L;
	entry.T = T;
	entry.type = type;
	m_Log.Add(entry);
	return TRUE;
}

BOOL CFIT_6204_Gorodilov_GreedyDoc::SaveLog(CString filePath) {
	CFile theFile;
	CFileException err;
	if (!theFile.Open(filePath, CFile::modeWrite | CFile::modeCreate, &err)){
		return FALSE;
	}
	CArchive ar(&theFile, CArchive::store);
	CString buf;

	buf.Format("%d %d\n", m_ScrollSize.cx, m_ScrollSize.cy);
	ar.WriteString(buf);
	for (int i = 0; i < m_Log.GetCount(); i++) {
		LOGENTRY entry = m_Log[i];
		buf.Format("%d %lf %lf G%d\n", entry.N, entry.L, entry.T, entry.type + 1);
		ar.WriteString(buf);	
	}
	buf = "node\n";
	ar.WriteString(buf);
	for (int i = 0; i < m_Points.GetCount(); i++) {
		CPoint p = m_Points[i];
		buf.Format("%d %d\n", p.x, p.y);
		ar.WriteString(buf);	
	}
	ar.Close();
	theFile.Close();
	return TRUE;
}